let data = [11, 3, 5, 1, 44, 12, 33, 66, 14, 22, 15];
// 冒泡
// 思路：每次遍历会把最大的一项拍到最后，然后对其他的再出进行遍历；
// 时间复杂度：O(n*n)
// 空间复杂度：O(1)
// 稳定
function bubblin(data) {
  for (let i = 0; i < data.length; i++) {
    for (let j = 0; j < data.length - 1 - i; j++) {
      if (data[j] > data[j + 1]) {
        var a = data[j + 1];
        data[j + 1] = data[j];
        data[j] = a;
      }
    }
  }
  return data;
}

// console.log(bubblin(data))

// [11, 3, 5, 1, 44, 12, 33, 66, 14, 22, 15];
// 选择排序
/**
 * 思路： 遍历一次把最小的和第一位交换，然后排除第一位，把剩下的当作一个数组重复操作
 * 时间复杂度：O(n*n)
 * 空间复杂度：O(1)
 * 不稳定
 */
function selectionSort(data) {
  let index = 0,
    sum;
  for (let n = 0; n < data.length; n++) {
    sum = data[n];
    index = n;
    for (let i = n; i < data.length; i++) {
      if (sum > data[i]) {
        sum = data[i];
        index = i;
      }
    }
    let a = data[index];
    data[index] = data[n];
    data[n] = a;
  }
  return data;
}
// console.log(selectionSort(data))

// [11, 3, 5, 1, 44, 12, 33, 66, 14, 22, 15];
// 插入排序
/**
 * 思路：第一项默认为已排序，从第二项开始，和前一项比较，后者小则交换，再和前面一项比较，直到大于、等于或到达第一位，则回到循环，执行下一次
 * 时间复杂度：O(n*n)
 * 空间复杂度：O(1)
 * 不稳定
 */
function insertionSort(data) {
  let num = 1;
  for (let i = num; i < data.length; i++) {
    let count = data[i];
    num = i;
    while (count < data[num - 1] && num >= 0) {
      data[num] = data[num - 1];
      data[num - 1] = count;
      num--;
    }
  }
  return data;
}
// console.log(insertionSort(data))

// [11, 3, 5, 1, 44, 12, 33, 66, 14, 22, 15];
// 快速排序
/**
 * 思路：选中一个目标target，把大于target的放右边，小于的放左边，在把左边和右边当作单独的数组，重复以上操作
 * 时间复杂度：nlog(n)
 * 空间复杂度：log(n)
 * 不稳定：和选择的target有关，选中中间值，会减小复杂度
 */
function querySort(data, leftIndex, rightIndex) {
  if (rightIndex - leftIndex < 2) return;
  let target = data[leftIndex],
    l = leftIndex,
    r = rightIndex;
  while (l < r) {
    while (target < data[r] && l < r) {
      r--;
    }
    data[l] = data[r];
    while (target > data[l] && l < r) {
      l++;
    }
    data[r] = data[l];
    data[l] = target
  }
  querySort(data, leftIndex, l - 1);
  querySort(data, l + 1, rightIndex);
  return data;
}
// console.log(querySort(data, 0, data.length - 1))

// [11, 3, 5, 1, 44, 12, 33, 66, 14, 22, 15];
//  归并排序
/**
 * 思路：数组对半切个成最小单位，两个最小单位进行排序组合，重复排序组合的过程
 * 时间复杂度：nlog(n)
 * O(n)
 * 不稳定：和选择的target有关，选中中间值，会减小复杂度
 */
function merge(data1, data2) {
    let result = [];
    while (data1.length && data2.length) {
        if (data1[0] < data2[0]) {
            result.push(data1.shift())
        } else {
            result.push(data2.shift())
        }
    }
    if (data1.length) {
        result = [...result, ...data1]
    }
    if (data2.length) {
        result = [...result, ...data2]
    }
    return result;
}
function mergeSort(data) {
    if (data.length < 2) return data;
    const middle = Math.floor(data.length / 2);
    const leftData = data.slice(0, middle);
    const rightData = data.slice(middle);
    return merge(mergeSort(leftData), mergeSort(rightData))
}

console.log(mergeSort(data))